// Gabriel Tessaroli   - 4321450
// Lucas Nunes Arvani  - 7986802
// Lucas Fúrio Franco  - 6793010

#include <queue>
#include <stdio.h>
#include <cstdlib>
#include <string.h>

#include <omp.h>

// criado para auxiliar a inserção no struct
#define assign(a,b,c) a.vertice = b; a.distance = c

using namespace std;

// criado para fazer a relação de duas vértices e sua distancia
typedef struct {

	int vertice;
	int distance;

} neighbor;

// classe usada para setar a posicao do
// novo valor a ser inserido fila de prioridade
class compare{
private:
	int *dist;
public:
	compare(int *a) { this->dist = a; }

	bool operator() (const int& a, const int& b) {
		return dist[a] > dist[b];
	}
};

int main(int argc, char *argv[]) {

	// numero de vertices, e numero de ligaçoes
	int n_vertices, n_edges;

	//'x' e 'y' são auxiliares que representam os cruzamentos
	//'dist' é a distancia entre os pontos x e y
	int x, y, dist;
	int i, j;		// auxiliares para interações
	neighbor n, _n;

	// inicializa grafo (uma matriz)
	vector<vector < neighbor > > graph;

	// pega numero de cruzamentos e de ruas
	scanf("%d %d", &n_vertices,  &n_edges);

	// cria o primeiro vetor de cidades
	for(i=0; i<n_vertices; ++i)
		graph.insert(graph.end(), vector<neighbor >());

	// monta o grafo, marcando as ligações entre os cruzamentos e suas distancias
	for(i=0; i<n_edges; ++i) {
		// pega os dois cruzamentos e a distancia entre eles
		scanf("%d %d %d", &x, &y, &dist);
		// decrementa x e y, pois vetor começa do 0
		x--; y--;

		// n.vertice = y
		// n.dist = dist
		// n é auxiliar.
		assign (n, y, dist);

		// entra na posição do cruzamento 'x' e insere 'n' (sua relação com o cruzamento 'y')
		graph.at(x).insert(graph.at(x).end(), n);

		// entra na posição do cruzamento 'y' e insere 'n' (sua relação com o cruzamento 'x')
		n.vertice = x;
		graph.at(y).insert(graph.at(y).end(), n);
	}

	// seta o numero de threads
	omp_set_num_threads(10);

	// inicializa vetor para armazenar maiores distancias de cada vertice
	int *max = (int *) malloc(sizeof(int) * n_vertices);

	// Inicializa processo em paralelo
	#pragma omp parallel
	{
		#pragma omp for private (j, n, _n)

		// cria distance e visit para cada thread para
		// não haver conflito com outras threads
		for(i=0; i<n_vertices; ++i) {
			int *distance = (int *) malloc(sizeof(int) * n_vertices);
			int *visit = (int *) malloc(sizeof(int) * n_vertices);

			// Inicializa a fila de prioridade
			priority_queue<int, vector<int>, compare> neighborhood (distance);

			// Seta valores iniciais para a realização do Dijkstra
			for(j=0; j<n_vertices; ++j) {
				distance[j] = -1;
				visit[j] = 0;
			}

			// Atribui um ponto inicial, que é a distancia do vértice
			// até ele mesmo, ou seja, a distancia será de zero.
			assign(n, i, 0);

			// insere na fila o primeiro valor.
			neighborhood.push(i);

			// atribui na tabela de distancia, o valor até ele mesmo
			// que será zero. E marca como visitado a vértice
			distance[i] = 0; visit[i] = 1;
			int _max = 0;

			// Enquanto tiver alguma vértice na fila ele realiza o algoritmo
			while(!neighborhood.empty()) {

				// pega o vértice com maior prioridade
				n.vertice = neighborhood.top();
				n.distance = distance[n.vertice];

				// retira vértice da fila
				neighborhood.pop();

				// marca vértice como visitado
				visit[n.vertice] = 1;
				// verefica se é o maior caminho
				if (n.distance > _max) _max = n.distance;

				// verefica todos os caminhos conectados com o vértice
				for(j=0; j<graph.at(n.vertice).size(); ++j) {

					// _n recebe um vértice ligado ao vértice 'n'
					_n = graph.at(n.vertice).at(j);

					// seta nova distancia caso ela seja menor que o atual
					if ((!visit[_n.vertice]) &&
						(distance[_n.vertice] == -1 || distance[_n.vertice] > (_n.distance + n.distance)) ) {
						_n.distance = _n.distance + n.distance;
						distance[_n.vertice] = _n.distance;
						neighborhood.push(_n.vertice);
					}

				}

			}

			// coloca na posição do vértice de origem a maior distancia encontrada.
			max[i] = _max;
			// libera memoria
			free(distance);
			free(visit);
		}
	}

	// verefica todos os maiores caminhos de cada vértice origem
	// e pega o vértice com o menor dentre eles. Este será o de melhor localidade.
	int min = max[0];
	for(i=0; i<n_vertices; ++i)
		if (min > max[i])
			min = max[i];

	// libera memoria
	free(max);


	printf("%d\n", min);


	return 0;
}
